class Solution {
public:
    int waysToStep(int n) {
        if (n == 1)
            return 1;
        else if (n == 2)
            return 2;
        else if (n == 3)
            return 4;
        // n >= 4
        int a = 1;
        int b = 2;
        int c = 4;
        int res = 0;
        n -= 3;
        while (n--)
        {
            res = (a + (b + c) % 1000000007) % 1000000007;
            a = b;
            b = c;
            c = res;
        }
        return res;
    }
};